package com.year_23.april;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 *
 *      1042 不邻街值花 : https://leetcode.cn/problems/flower-planting-with-no-adjacent/
 *
 *
 *
 * @Author jsh
 * @Date 2023/4/15 23:15
 * @Version 1.0
 */
public class Day15 {

    public static void main(String[] args) {
        int n = 5;
        int[][] paths = {{4,1},{4,2},{4,3},{2,5},{1,2},{1,5}};
        int[] ints = gardenNoAdj(n, paths);
        for (int anInt : ints) {
            System.out.println(anInt);
        }
    }

    public static int[] gardenNoAdj(int  n, int[][] paths){
        List<Integer>[] lists = new List[n];

        for (int i = 0; i < lists.length; i++) {
            lists[i] = new ArrayList<Integer>();
        }

        for (int[] path : paths){
            lists[ path[0] - 1].add(path[1] - 1);
            lists[ path[1] - 1].add(path[0] - 1);
        }
        //记录花园的花种
        int[] ans = new int[n];
        //Arrays.fill(ans, 0);

        for (int i = 0; i < n; i++) {
            //记录花园i 周围的花园种植的花种
            boolean[] b = new boolean[5];
            lists[i].forEach(f ->{
                b[ans[f]] = true;
            });

            //遍历周围的花园，种植周围未种植的花种
            for (int j = 1; j <= 4; j++) {
                if (!b[j]){
                    ans[i] = j;
                    break;
                }
            }
        }
        return ans;
    }
}
